let origin = [
  { id: 1 },
  { id: 2 },
  { id: 3 },
  { id: 11, pid: 1 },
  { id: 12, pid: 1 },
  { id: 111, pid: 11 },
  { id: 112, pid: 11 },
  { id: 21, pid: 2 },
  { id: 31, pid: 3 },
];

function buildTreeIterative(data) {
  const map = {};
  const result = [];

  // 1. 先把所有节点存到 map 中
  data.forEach((item) => {
    map[item.id] = { ...item }; // 克隆对象
  });

  // 2. 遍历所有节点，挂到父节点下
  data.forEach((item) => {
    if (item.pid) {
      const parent = map[item.pid];
      if (parent) {
        parent.children = parent.children || [];
        parent.children.push(map[item.id]);
      }
    } else {
      // 没有 pid 的就是根节点
      result.push(map[item.id]);
    }
  });

  return result;
}

const tree = buildTreeIterative(origin);

console.log(JSON.stringify(tree, null, 2));
